#ifndef STX_ALGORITHM_INPLACE_MERGE_HPP
#define STX_ALGORITHM_INPLACE_MERGE_HPP

#include <stx/algorithm/common.hpp>
#include <stx/core/scoped_ptr.hpp>
#include <stx/algorithm/merge.hpp>
#include <stx/algorithm/move.hpp>
#include <stx/algorithm/move_iterator.hpp> //todo: move out from algorithms
#include <stx/algorithm/upper_bound.hpp>
#include <stx/algorithm/lower_bound.hpp>
#include <stx/algorithm/rotate.hpp>
#include <stx/algorithm/min.hpp>

namespace stx {

template <class Compare, class BidirectionalIterator>
inline void
buffered_inplace_merge_impl(
    BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last,
    Compare comp,
    typename std::iterator_traits<BidirectionalIterator>::difference_type len1,
    typename std::iterator_traits<BidirectionalIterator>::difference_type len2,
    typename std::iterator_traits<BidirectionalIterator>::value_type* buff)
{
    typedef typename std::iterator_traits<BidirectionalIterator>::value_type value_type;
    typedef typename std::iterator_traits<BidirectionalIterator>::difference_type difference_type;
    typedef typename std::iterator_traits<BidirectionalIterator>::pointer pointer;
    destruct_n d(0);
    scoped_ptr<value_type, destruct_n&> h2(buff, d);
    if (len1 <= len2) {
        value_type* p = buff;
        for (
            BidirectionalIterator i = first;
                i != middle;
                d.incr((value_type*)0), ++i, ++p) {
            ::new(p) value_type(stx::move(*i));
        }
        stx::merge_impl<Compare>(
            move_iterator<value_type*>(buff),
            move_iterator<value_type*>(p),
            move_iterator<BidirectionalIterator>(middle),
            move_iterator<BidirectionalIterator>(last),
            first,
            comp);
    } else {
        value_type* p = buff;
        for (BidirectionalIterator i = middle; i != last; d.incr((value_type*)0), ++i, ++p) {
            ::new(p) value_type(stx::move(*i));
        }
        typedef std::reverse_iterator<BidirectionalIterator> _RBi;
        typedef std::reverse_iterator<value_type*> _Rv;
        stx::merge_impl(
            move_iterator<_RBi>(_RBi(middle)),
            move_iterator<_RBi>(_RBi(first)),
            move_iterator<_Rv>(_Rv(p)),
            move_iterator<_Rv>(_Rv(buff)),
            _RBi(last), negate<Compare>(comp));
    }
}

template <class Compare, class BidirectionalIterator>
inline void
inplace_merge_impl(
    BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last,
    Compare comp,
    typename std::iterator_traits<BidirectionalIterator>::difference_type len1,
    typename std::iterator_traits<BidirectionalIterator>::difference_type len2,
    typename std::iterator_traits<BidirectionalIterator>::value_type* buff,
    std::ptrdiff_t buff_size)
{
    typedef typename std::iterator_traits<BidirectionalIterator>::value_type value_type;
    typedef typename std::iterator_traits<BidirectionalIterator>::difference_type difference_type;
    while (1) {
        // if middle == last, we're done
        if (len2 == 0) {
            return;
        }
        // shrink [first, middle) as much as possible (with no moves), returning if it shrinks to 0
        for (; true; ++first, --len1) {
            if (len1 == 0) {
                return;
            }
            if (comp(*middle, *first)) {
                break;
            }
        }
        if (len1 <= buff_size || len2 <= buff_size) {
            buffered_inplace_merge_impl<Compare>(first, middle, last, comp, len1, len2, buff);
            return;
        }
        // first < middle < last
        // *first > *middle
        // partition [first, m1) [m1, middle) [middle, m2) [m2, last) such that
        //     all elements in:
        //         [first, m1)  <= [middle, m2)
        //         [middle, m2) <  [m1, middle)
        //         [m1, middle) <= [m2, last)
        //     and m1 or m2 is in the middle of its range
        BidirectionalIterator m1;  // "median" of [first, middle)
        BidirectionalIterator m2;  // "median" of [middle, last)
        difference_type len11;     // distance(first, m1)
        difference_type len21;     // distance(middle, m2)
        // binary search smaller range
        if (len1 < len2) {
            // len >= 1, len2 >= 2
            len21 = len2 / 2;
            m2 = middle;
            stx::advance(m2, len21);
            m1 = upper_bound_impl<Compare>(first, middle, *m2, comp);
            len11 = stx::distance(first, m1);
        }
        else
        {
            if (len1 == 1)
            {   // len1 >= len2 && len2 > 0, therefore len2 == 1
                // It is known *first > *middle
                swap(*first, *middle);
                return;
            }
            // len1 >= 2, len2 >= 1
            len11 = len1 / 2;
            m1 = first;
            stx::advance(m1, len11);
            m2 = lower_bound_impl<Compare>(middle, last, *m1, comp);
            len21 = stx::distance(middle, m2);
        }
        difference_type len12 = len1 - len11;  // distance(m1, middle)
        difference_type len22 = len2 - len21;  // distance(m2, last)
        // [first, m1) [m1, middle) [middle, m2) [m2, last)
        // swap middle two partitions
        middle = stx::rotate(m1, middle, m2);
        // len12 and len21 now have swapped meanings
        // merge smaller range with recurisve call and larger with tail recursion elimination
        if (len11 + len21 < len12 + len22)
        {
            inplace_merge_impl<Compare>(first, m1, middle, comp, len11, len21, buff, buff_size);
//          inplace_merge_impl<Compare>(middle, m2, last, comp, len12, len22, buff, buff_size);
            first = middle;
            middle = m2;
            len1 = len12;
            len2 = len22;
        }
        else
        {
            inplace_merge_impl<Compare>(middle, m2, last, comp, len12, len22, buff, buff_size);
//          inplace_merge_impl<Compare>(first, m1, middle, comp, len11, len21, buff, buff_size);
            last = middle;
            middle = m1;
            len1 = len11;
            len2 = len21;
        }
    }
}

template <class T>
struct inplace_merge_impl_switch
{
    static const unsigned value = is_trivially_copy_assignable<T>::value;
};

template <class BidirectionalIterator, class Compare>
inline void
inplace_merge(
    BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last,
    Compare comp)
{
    typedef typename std::iterator_traits<BidirectionalIterator>::value_type value_type;
    typedef typename std::iterator_traits<BidirectionalIterator>::difference_type difference_type;
    difference_type len1 = stx::distance(first, middle);
    difference_type len2 = stx::distance(middle, last);
    difference_type buf_size = stx::min(len1, len2);
    std::pair<value_type*, std::ptrdiff_t> buf(0, 0);
    scoped_ptr<value_type, return_temporary_buffer_impl> h;
    if (inplace_merge_impl_switch<value_type>::value && buf_size > 8) {
        buf = stx::get_temporary_buffer<value_type>(buf_size);
        h.reset(buf.first);
    }
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return stx::inplace_merge_impl<comp_ref>(
        first,
        middle,
        last,
        comp,
        len1,
        len2,
        buf.first,
        buf.second);
}

template <class BidirectionalIterator>
inline void
inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
{
    stx::inplace_merge(
        first,
        middle,
        last,
        stx::less<typename std::iterator_traits<BidirectionalIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_INPLACE_MERGE_HPP
